import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
import java.util.Set;

public class SkipListMap<K extends Comparable<? super K>, V> implements IListMap<K, V> {
	protected CoinFlipper flipper;
	protected int size;
	protected Node<K,V> head;
	protected Node<K,V> tail;
	protected int height;

	/**
	 * constructs a SkipListMap object that stores keys in ascending order
	 * when a key value pair is inserted, the flipper is called until it returns a tails
	 * if for an pair the flipper returns n heads, the corresponding node has n + 1 levels
	 * 
	 * the skip list should have an empty node at the beginning and end that do not store any data
	 * these are called sentinel nodes  
	 * @param flipper the source of randomness 
	 */
	public SkipListMap(CoinFlipper flipper){
		this.flipper = flipper;
		this.head = new Node<K,V>(null,null);
		this.tail = new Node<K,V>(null,null);
		head.setNext(tail);
		tail.setPrev(head);
		Node<K,V> head_temp = head;
		Node<K,V> tail_temp = tail;

		for (int i=0;i<10;i++) {
			head_temp.setDown(new Node<K,V>(null,null));
			tail_temp.setDown(new Node<K,V>(null,null));
			head_temp.getDown().setUp(head_temp);
			tail_temp.getDown().setUp(tail_temp);
			head_temp.getDown().setNext(tail_temp.getDown());
			tail_temp.getDown().setPrev(head_temp.getDown());
			head_temp = head_temp.getDown();
			tail_temp = tail_temp.getDown(); }
		this.size = 0;
		this.height = 0;}

	@Override
	public K firstKey() {
		if (size==0) return null;
		Node<K,V> curr = head;
		while(curr.getDown()!=null) curr = curr.getDown();
		return curr.getNext().getKey(); }

	@Override
	public K lastKey() {
		if (size==0) return null;
		Node<K,V> curr = tail;
		while(curr.getDown()!=null) curr = curr.getDown();
		return curr.getPrev().getKey(); }

	@Override
	public boolean containsKey(K key) {
		if (size==0) return false;
		Node<K,V> curr = head;
		while (curr.getNext().getKey()==null) curr = curr.getDown();
		while (curr.getNext().getKey()!=null || curr.getDown()!=null) {
			while (curr.getNext().getKey()==null && curr.getNext().getKey().compareTo(key)<0) curr = curr.getDown();
			if (curr.getNext().getKey().compareTo(key)==0) return true;
			else
				while (curr.getNext().getKey()!=null && curr.getNext().getKey().compareTo(key)>0) curr = curr.getNext();
		}
		return false; }

	@Override
	public boolean containsValue(V value) {
		if (size==0) return false;
		Node<K,V> curr = head;
		while (curr.getNext().getKey()==null) curr = curr.getDown();
		while (curr.getNext().getKey()!=null) {
			if (curr.getNext().getValue().equals(value)) return true;
			curr = curr.getNext(); }
		return false;
	}

	/**
	 * {@link IListMap#put(Comparable, Object) IListMap}
	 * 
	 * if a node is updated, only the key value pair should be changed  
	 */
	@Override
	public V put(K key, V newValue) {
		int h = 1;
		while (flipper.flipCoin().equals(CoinFlipper.Coin.HEADS)) h++;
		List<Node<K,V>> list = new ArrayList<Node<K,V>>();
		for (int i=0;i<h;i++) {
			Node<K,V> newNode = new Node<K,V>(key,newValue);
			list.add(newNode);
			if (i!=0) {
				list.get(i-1).setUp(newNode);
				newNode.setDown(list.get(i-1));}
		}
		Node<K,V> curr = head;
		while (curr.getDown()!=null) curr = curr.getDown();

		if (size==0) {
			Node<K,V> a = curr;
			Node<K,V> b = curr.getNext();
			for (int i=0;i<h;i++) {
				b.setPrev(list.get(i));
				list.get(i).setNext(b);
				a.setNext(list.get(i));
				list.get(i).setPrev(a);

				a = a.getUp();
				b = b.getUp();}
			size++;
			return null;
		}

		while (curr.getNext().getKey()!=null && key.compareTo(curr.getNext().getKey())>=0) curr = curr.getNext();

		if (curr.getKey()!=null && curr.getKey().equals(key)) {
			V replaced = curr.getValue();
			while (curr!=null) {
				curr.setValue(newValue);
				curr = curr.getUp();
			}
			return replaced; 
		}

		Node<K,V> a = curr;
		Node<K,V> b = curr.getNext();

		for (int i=0;i<h;i++) {
			b.setPrev(list.get(i));
			list.get(i).setNext(b);
			a.setNext(list.get(i));
			list.get(i).setPrev(a);

			while (a.getUp()==null) a = a.getPrev();
			while (b.getUp()==null) b = b.getNext();

			a = a.getUp();
			b = b.getUp();
		}
		size++;
		return null;
	}

	@Override
	public V get(K key) {
		if (size==0) return null;
		Node<K,V> curr = head;
		while (curr.getNext().getKey()==null) curr = curr.getDown();
		while (curr.getNext().getKey()!=null || curr.getDown()!=null) {
			while (curr.getNext().getKey()==null && curr.getNext().getKey().compareTo(key)<0) curr = curr.getDown();
			if (curr.getNext().getKey().compareTo(key)==0) return curr.getNext().getValue();
			else
				while (curr.getNext().getKey()!=null && curr.getNext().getKey().compareTo(key)>0) curr = curr.getNext();
		}
		return null; }

	@Override
	public int size() {
		return size;
	}

	@Override
	public void clear() {
		this.head = new Node<K,V>(null,null);
		this.tail = new Node<K,V>(null,null);
		head.setNext(tail);
		tail.setPrev(head);
		Node<K,V> head_temp = head;
		Node<K,V> tail_temp = tail;

		for (int i=0;i<10;i++) {
			head_temp.setDown(new Node<K,V>(null,null));
			tail_temp.setDown(new Node<K,V>(null,null));
			head_temp.getDown().setNext(tail_temp);
			tail_temp.getDown().setPrev(head_temp);
			head_temp = head_temp.getDown();
			tail_temp = tail_temp.getDown(); }
		this.size = 0;
		this.height = 0;
	}

	@Override
	public Set<K> keySet() {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public Collection<V> values() {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public V remove(K key) {
		// TODO Auto-generated method stub
		return null;
	}

	@SuppressWarnings("hiding")
	private class Node<K,V> {

		private K key;
		private V value;
		private Node<K,V> next;
		private Node<K,V> prev;
		private Node<K,V> down;
		private Node<K,V> up;

		private Node(K key, V value) {
			this.key = key;
			this.value = value;
			this.next = null;
			this.prev = null;
		}

		private K getKey() {
			return key;
		}

		private V getValue() {
			return value;
		}

		private void setValue(V value) {
			this.value = value;
		}

		private Node<K,V> getNext() {
			return next;
		}

		private void setNext(Node<K,V> next) {
			this.next = next;
		}

		private Node<K,V> getPrev() {
			return prev;
		}

		private void setPrev(Node<K,V> prev) {
			this.prev = prev;
		}

		private Node<K,V> getDown() {
			return down;
		}

		private void setDown(Node<K,V> down) {
			this.down = down;
		}

		private Node<K,V> getUp() {
			return up;
		}

		private void setUp(Node<K,V> up) {
			this.up = up;
		}
	}

}